package DP;

/**
 * https://www.lintcode.com/problem/coins-in-a-line/description
 */
public class CoinsInline {

    //这个容易比较绕，但是，看看代码就好理解了。
    public boolean firstWillWin(int n) {
        boolean[] dp = new boolean[n+1];
        if(n == 0){
            return false;
        }
        if(n == 1){
            return true;
        }

        dp[0]=false;
        dp[1]=true;

        for(int i=2; i<=n; i++){
            //有四种情况，在拿第i个的时候，要看，我们要看上一个拿的人 四种情况，来判断，我当前拿的情况，有点绕
            //f[i] = f[i-1] == true && f[i-2] == true   必败，因为上一次拿的人都是胜利的
            //f[i] = f[i-1] == true && f[i-2] == true   必胜，因为上一次拿的人，有一种情况是失败的，我会选让
            //f[i] = f[i-1] == false && f[i-2] == true 必胜,因为上一次拿的人，有一种情况是失败的，我会选让
            //f[i] = f[i-1] == false && f[i-2] == false 上一次拿的人都是必败的，拿我怎么拿都是必胜的
            if( dp[i-1] && dp[i-2] ){
                dp[i] = false;
            }else if(!dp[i-1] || !dp[i-2]){
                dp[i] = true;
            }
        }

        return dp[n];
    }

    public boolean firstWillWin2(int[] values) {
        /*
        https://www.lintcode.com/problem/coins-in-a-line-ii/note/209695
        状态:设f[i]为一方在面对a[i..n-1]这些数字时，能得到的最大的与对手的数字差 • 转移方程:f[i] = max{a[i] - f[i+1], a[i] + a[i + 1] - f[i + 2]}
• 初始条件:f[n] = 0
• 计算顺序:f[n], f[n-1], ..., f[0]
• 如果f[0]>=0，先手Alice必赢，否则必输

根据我的理解 f[i]这里的含义是 在i位置处的先手向后进行完毕该游戏（从i一直到n-1）时 所能获得的最大差值（先手减去后手）


https://www.lintcode.com/problem/coins-in-a-line-ii/note/194850
         方法一
转移方程 f[i] = sum - MIN{f[i - 1], f[i - 2]}

从左向右循环
sum是至今遇到所有数的和
f[i]是如果取走第i - 1颗或第i - 1和第i - 2颗硬币之后手上硬币的总价值
最后看手上的总价值是否超过半数
方法二
转移方程 f[i] = MAX{values[i] - f[i + 1], values[i] + values[i + 1] - f[i + 2]}

从右向左循环
f[i]是当前手上的价值和对方手上价值的差
如果f[i] > 0，表示当前是赢的状态
如果f[i] = 0，表示当前打平手
如果f[i] < 0，表示当前是输的状态
最后看f[0]是否大于0

         */
        int[] dp = new int[values.length];
        for (int i = values.length - 1; i >= 0; i--) {
            if (i == values.length - 1) {
                dp[i] = values[i];
            } else if (i == values.length - 2) {
                dp[i] = values[i] + values[i + 1];
            } else {
                dp[i] = Math.max(values[i] - dp[i + 1], values[i] + values[i + 1] - dp[i + 2]);
            }
        }

        return dp[0] >= 0;
    }

    //这题的重点是，对手拿到的钱减去我要拿的，如果我最后的金额是 >0的，那么 先手就是必胜！！
    public boolean firstWillWin2new(int[] values) {
        if (values == null || values.length == 0) return false;
        int n = values.length;
        int[] dp = new int[values.length+1];
        dp[0] = values[0];dp[1] = values[0] + values[1];

        for(int i=2; i < n; i++){
            //如果第i个硬币的金额 比 对手拿到的金币多，那就是结果
            dp[i] = Math.max(values[i] - dp[i-1], values[i] + values[i-1] - dp[i-2]);
        }

        return dp[n-1] >= 0;
    }

    /**
     * 用求和方式计算下来，然后，一个dp存储当前拿到的最大的数字
     * 还没做出来。 貌似 那种互减的会好点
     * https://www.lintcode.com/problem/coins-in-a-line-ii/note/194850
     */
//    public boolean firstWillWin2_sum(int[] values) {
//        if (values == null || values.length == 0) return false;
//        int n = values.length;
//        int[] dp = new int[values.length];
//        dp[0] = values[0];dp[1] = values[0] + values[1];
//        int sum = values[0] + values[1];
//
//        for(int i=2; i < n; i++){
//            sum += values[i];
//            dp[i] = Math.max(dp[i-1] + values[i], dp[i-2] + values[i]);
//        }
//
//        return dp[n-1] > (sum / 2);
//    }

    /**
     * 这道题是要VIP的，然后，规则是
     * 每次可以选取头，或者选尾，问最后谁的金额多谁获胜
     *
     * 这题的重点是，对手拿到的钱减去我要拿的，如果我最后的金额是 >0的，那么 先手就是必胜！！
     * 因为有从头和从尾拿两种方式，所以，弄一个二维的
     * DP[i][j]表示，第i次拿第j个硬币的时候
     */
    public boolean firstWillWinIII(int[] A){
        if (A == null || A.length == 0) return false;
        int n = A.length;
        int[][] dp = new int[A.length][A.length];
        //先初始化，跟回文那题是一样的思想
        for(int i=0; i<n;i++){
            dp[i][i] = A[i];
        }
        int i,j,len;
        for( len=2; len<n;len++){
            for( i=0; i<n-len; i++){
                j=i+len-1;
                //f[i][j] 表示一方先手在面对A[i...j]这些数字时，能得到的最大的与对手的差
                //这个跟回文那个很像
                dp[i][j] = Math.max(A[i]-dp[i+1][j], A[j]-dp[i][j-1]);
            }
        }

        return dp[0][n-1] >= 0;
    }

    public static void main(String[] args){
        CoinsInline c = new CoinsInline();
        int[] a = {1,2,4};



    }


}
